package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 双端队列
 */
public class _08_二叉树的按层的ZigZag打印 {

    public static void zigZagPrint(TreeNode root) {

        if (root == null) {

            return;
        }


        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);

        int level = 1;
        int levelCount = 1;
        while (!deque.isEmpty()) {

            boolean flag = ((level & 1) == 1);

            if (flag) {

                TreeNode node = deque.removeFirst();
                System.out.print(node.val+",");

                if (node.left != null) {

                    deque.addLast(node.left);
                }

                if (node.right != null) {

                    deque.addLast(node.right);
                }

            }else {

                TreeNode node = deque.removeLast();
                System.out.print(node.val + ",");

                if (node.right != null) {

                    deque.addFirst(node.right);
                }

                if (node.left != null) {

                    deque.addFirst(node.left);
                }

            }

            levelCount -=1;

            if (levelCount == 0) {
                System.out.println();
                levelCount = deque.size();
                level += 1;
            }
        }


    }


    public static void main(String[] args) {

        TreeNode root = new TreeNode(6);

        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);

        root.right = new TreeNode(12);
        root.right.left = new TreeNode(10);
        root.right.left.left = new TreeNode(4);
        root.right.left.left.left = new TreeNode(2);
        root.right.left.left.right = new TreeNode(5);
        root.right.left.right = new TreeNode(14);
        root.right.left.right.left = new TreeNode(11);
        root.right.left.right.right = new TreeNode(15);

        root.right.right = new TreeNode(13);
        root.right.right.left = new TreeNode(20);
        root.right.right.right = new TreeNode(16);


        zigZagPrint(root);
    }

}
